//////////////////////////////////////////////////////////////////////////////////////////////////////
// 项目名   : ThreadManagement
// 文件名   : Parallel_Accumulate.h
// 作者     : Aiye
// 日期     : 2025/9/17 19:50
// 邮箱     : 2878548868@qq.com
// 摘要     : 并行算法
//////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef THREADMANAGEMENT_PARALLEL_ACCUMULATE_H
#define THREADMANAGEMENT_PARALLEL_ACCUMULATE_H
#include <iterator>
#include <numeric>
#include <thread>
#include <vector>

/// @brief 并行累加算法，将区间分块后用多线程并行计算总和
/// @tparam Iterator 输入迭代器类型
/// @tparam T 累加结果类型
/// @param begin 区间起始迭代器
/// @param end 区间结束迭代器
/// @param init 初始累加值
/// @return 区间所有元素累加后的结果
template<typename Iterator, typename T>
T parallel_accumulate(Iterator begin, Iterator end, T init)
{
    const size_t length = std::distance(begin, end); // 计算区间长度
    if (length == 0) return init; // 空区间直接返回初始值

    constexpr size_t min_per_thread = 1000;   // 每个线程最少处理的元素数
    const size_t max_threads = (length + min_per_thread - 1) / min_per_thread; // 能用的最大线程数（按区块数计算）
    const size_t hardware_threads = std::thread::hardware_concurrency(); // 获取硬件支持的线程数
    const size_t num_threads = std::min(hardware_threads != 0 ? hardware_threads : 2, max_threads); // 实际使用的线程数，不能超过最大线程数
    const size_t block_size = length / num_threads; // 每个线程处理的区块大小

    std::vector<T> results(num_threads); // 存储每个线程的累加结果
    std::vector<std::thread> threads(num_threads - 1); // 存储线程对象，主线程处理最后一块，所以只创建 num_threads-1 个线程

    Iterator block_start = begin;
    for (size_t i = 0; i < (num_threads - 1); ++i)  // 创建子线程，分别处理各自的区块
    {
        Iterator block_end = block_start;
        std::advance(block_end, block_size); // 移动到当前区块末尾
        threads[i] = std::thread([block_start, block_end, &results, i]()
        {
            results[i] = std::accumulate(block_start, block_end, T{}); // 子线程累加自己的区块
        });
        block_start = block_end; // 下一个区块起点
    }
    results[num_threads - 1] = std::accumulate(block_start, end, T{}); // 主线程处理最后一个区块

    for (auto& t : threads) t.join(); // 等待所有子线程完成

    return std::accumulate(results.begin(), results.end(), init); // 汇总所有区块的累加结果
}

#endif //THREADMANAGEMENT_PARALLEL_ACCUMULATE_H
